package sit.engreal.leetcode.weekly;

import org.junit.jupiter.api.Assertions;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Contest312 {
    public String[] sortPeople(String[] names, int[] heights) {
        final int n = names.length;
        final ArrayList<Integer> id = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            id.add(i);
        }
        id.sort(Comparator.comparingInt(i -> -heights[i]));
        final String[] strings = new String[n];
        for (int i = 0; i < n; i++) {
            strings[i] = names[id.get(i)];
        }
        return strings;
    }

    public static void testSortPeople() {
        final Contest312 demo = new Contest312();
        {
            final String[] names = demo.sortPeople(new String[]{"GXLVEHVABFOGSFXUYYR", "TUHxnsxmu", "X", "OOYBLVKmzlaeaxbprc", "ARNLAPtfvmutkfsa", "XPMKPDUWOQEEILtbdjip", "QICEutjbr", "R"},
                    new int[]{11578, 89340, 73785, 12096, 55734, 89484, 59775, 72652});
            System.out.println(Arrays.toString(names));
            Assertions.assertArrayEquals(new String[]{"XPMKPDUWOQEEILtbdjip", "TUHxnsxmu", "X", "R", "QICEutjbr", "ARNLAPtfvmutkfsa", "OOYBLVKmzlaeaxbprc", "GXLVEHVABFOGSFXUYYR"},
                    names);
        }
        {
            final String[] names = demo.sortPeople(new String[]{"Mary", "John", "Emma"},
                    new int[]{180, 165, 170});
            System.out.println(Arrays.toString(names));
            Assertions.assertArrayEquals(new String[]{"Mary", "Emma", "John"},
                    names);
        }
        {
            final String[] names = demo.sortPeople(new String[]{"Alice", "Bob", "Bob"},
                    new int[]{155, 185, 150});
            System.out.println(Arrays.toString(names));
            Assertions.assertArrayEquals(new String[]{"Bob", "Alice", "Bob"},
                    names);
        }

    }

    public int longestSubarray(int[] nums) {
        int value = 0;
        int step = 1;
        int i = 0;
        int j = 1;
        while (j < nums.length) {
            if (nums[i] != nums[j]) {
                if (nums[i] > value) {
                    value = nums[i];
                    step = j - i;
                } else if (nums[i] == value) {
                    step = Math.max(step, j - i);
                }
                i = j;
            }
            j++;
        }

        if (nums[i] > value) {
            step = j - i;
        } else if (nums[i] == value) {
            step = Math.max(step, j - i);
        }
        return step;
    }

    public static void longestSubarrayTest() {
        final Contest312 demo = new Contest312();

        Assertions.assertEquals(1,
                demo.longestSubarray(new int[]{96317, 96317, 96317, 96317, 96317, 96317, 96317, 96317, 96317, 279979}));
        Assertions.assertEquals(1,
                demo.longestSubarray(new int[]{100, 5, 5}));

        Assertions.assertEquals(2,
                demo.longestSubarray(new int[]{1, 2, 3, 3, 2, 2}));

        Assertions.assertEquals(1,
                demo.longestSubarray(new int[]{1, 2, 3, 4}));
    }

    public List<Integer> goodIndices(int[] nums, int k) {
        final int n = nums.length;
        final ArrayList<Integer> indices = new ArrayList<>();
        if (k * 2 + 1 > n) {
            return indices;
        }
        final int[] left = new int[n];
        int i, j;
        for (i = 0, j = 1; j < n; j++) {
            left[j] = j - i;
            if (nums[j] > nums[j - 1]) {
                i = j;
            }
        }
        final int[] right = new int[n];
        for (i = n - 1, j = n - 2; j >= 0; j--) {
            right[j] = i - j;
            if (nums[j] > nums[j + 1]) {
                i = j;
            }
        }

        for (i = 0; i < n; i++) {
            if (left[i] >= k && right[i] >= k) {
                indices.add(i);
            }
        }

        System.out.println(Arrays.toString(left));
        System.out.println(Arrays.toString(right));

        return indices;
    }

    public static void goodIndicesTest() {
        final Contest312 demo = new Contest312();

        Assertions.assertEquals(
                IntStream.of(4, 5).boxed().collect(Collectors.toList()),
                demo.goodIndices(new int[]{878724, 201541, 179099, 98437, 35765, 327555, 475851, 598885, 849470, 943442}, 4)
        );

        Assertions.assertEquals(
                IntStream.of(2, 3).boxed().collect(Collectors.toList()),
                demo.goodIndices(new int[]{2, 1, 1, 1, 3, 4, 1}, 2)
        );


        Assertions.assertEquals(
                new ArrayList<Integer>(),
                demo.goodIndices(new int[]{2, 1, 1, 2}, 2)
        );
    }

    public static void main(String[] args) {
        goodIndicesTest();
        longestSubarrayTest();
        testSortPeople();
    }
}
